1. Field of the Invention
The invention relates to techniques for optimizing write/erase operations in memory/storage devices, and was developed by paying specific attention to the possible application in “flash” memories.
2. Description of the Related Art
Flash memories are non-volatile storage devices, able to store recorded data without a power source. A computer program using the ability of a flash memory to be erased and reprogrammed can modify the data stored in a flash memory. These basic capabilities have made flash memories suitable for acting as standard storage media in computer systems, i.e. as flash disks.
Flash devices are typically partitioned in several contiguous zones, each of which is individually erasable. Such zones are known under various designations, such as units or blocks. For the sake of clarity, in the following description they will be referred to as blocks or erase units.
A limitation of flash memory technology lies in that the number of times a block can be erased is intrinsically limited by the physics of the flash cell. Repeated erasure of a block wears out the cells in the unit leading to a reduced capability to distinguish between the erased state and the programmed state. This results in a longer time being required to erase the unit, and to the appearance of sporadic faults in programming or erasing data. The unit may ultimately entirely lose its ability of being erased and reprogrammed.
The effects of wear are statistical in nature, and the ability of a flash device to withstand wear is usually described in terms of a number called the program/erase endurance. This number is the minimum or average number of times each flash unit can be erased without encountering significant failures. Vendor endurance numbers currently range from tens of thousands to a million.
The limited endurance limits the lifetime of a flash disk. It would be advantageous to have a lifetime that is as long as possible, and this depends on the pattern of access to the flash disk. Repeated and frequent writes to a single block or a small number of blocks will end the useful lifetime of the media quickly. On the other hand, if writes can be evenly distributed to all blocks of the media, each block will be capable of coming close to the maximum number of erases it can endure. The onset of failures will thus be delayed as much as possible, maximizing the lifetime of the media.
Flash disk managers typically employ algorithms that give them discretion over the physical location where new data will be written, and they direct written data in such a way to guarantee that different flash units will be subjected to the same number of erases. Such a procedure is known in the art as “wear leveling”. Some managers record the number of erases a unit has experienced in a register in that unit, and enforce a procedure intended to guarantee that the variation in the number of erases of each unit will not exceed some small constant. Other arrangements use a randomization of the choice of the target unit, and rely on statistics and the law of large numbers to maintain an even wear across the flash media.